import java.util.*;
public class SortingAlgorithms1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 提示用户输入或随机生成序列
        System.out.println("请选择输入方式：1. 手动输入 2. 随机生成");
        int choice = scanner.nextInt();
        int[] array;
        if (choice == 1) {
            // 手动输入序列
            System.out.println("请输入序列长度：");
            int length = scanner.nextInt();
            array = new int[length];
            System.out.println("请输入不重复的数字序列：");//输入方式是数字加空格再打数字
            for (int i = 0; i < length; i++) {
                array[i] = scanner.nextInt();
            }
        } else {
            // 随机生成序列
            System.out.println("请输入你要进行排序的数字个数：");
            int num = scanner.nextInt();
            array = new int[num];
            int k = 0;
            while (k < num) {
                int t = (int) (Math.random() * 1000); // 随机产生0-1000范围内的数字，并确保不重复
                boolean b = false;
                for (int i = 0; i < k; i++) { // 检查生成的数字是否重复
                    if (t == array[i]) {
                        b = true;
                        break;
                    }
                }
                if (!b) {
                    array[k] = t;
                    k++;
                }
            }
        }
        // 提示用户选择排序方法
        System.out.println("请输入你要使用的排序方法（1-8），用空格分隔（例如：1 3 5）：");
        scanner.nextLine(); // 清理输入缓冲区
        String choiceStr = scanner.nextLine();
        String[] choices = choiceStr.split(" "); // 将输入的字符串按空格分割成数组
        // 根据用户选择执行相应的排序算法
        for (String method : choices) {
            int[] sortedArray = array.clone(); // 克隆原始数组以避免修改原始数据
            switch (method) {
                case "1":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行直接插入排序");
                    int[] b = InserSort(sortedArray);
                    System.out.println("经过直接插入排序后最终状态： " + Arrays.toString(b));
                    break;
                case "2":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行冒泡排序");
                    int[] c = BubbleSort(sortedArray);
                    System.out.println("经过冒泡排序后最终状态： " + Arrays.toString(c));
                    break;
                case "3":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行希尔排序");
                    int[] d = ShellSort(sortedArray);
                    System.out.println("经过希尔排序后最终状态： " + Arrays.toString(d));
                    break;
                case "4":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行快速排序");
                    QuickSort(sortedArray, 0, sortedArray.length - 1);
                    System.out.println("经过快速排序后最终状态： " + Arrays.toString(sortedArray));
                    break;
                case "5":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行基数排序");
                    radixSort(sortedArray);
                    System.out.println("经过基数排序后最终状态： " + Arrays.toString(sortedArray));
                    break;
                case "6":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行归并排序");
                    mergeSort(sortedArray, 0, sortedArray.length - 1);
                    System.out.println("经过归并排序后最终状态： " + Arrays.toString(sortedArray));
                    break;
                case "7":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行选择排序");
                    selectionSort(sortedArray);
                    System.out.println("经过选择排序后最终状态： " + Arrays.toString(sortedArray));
                    break;
                case "8":
                    System.out.println("初始状态： " + Arrays.toString(sortedArray) + " 下面进行 TimSort 排序");
                    timSort(sortedArray);
                    System.out.println("经过 TimSort 排序后最终状态： " + Arrays.toString(sortedArray));
                    break;
                default:
                    System.out.println("无效的选择：" + method);
            }
        }
        scanner.close();
    }
    // 直接插入排序算法
    public static int[] InserSort(int[] a) {
        int i, j, num = 0;
        // 从第二个值开始，遍历所有值
        for (i = 1; i < a.length; i++) {
            // 每次排序a[i]与前面的所有值比较
            for (j = 0; j < i; j++) {
                // 如果a[j]大于a[i]，则前面的数据不动
                if (a[i] < a[j]) {
                    // 如果a[i]小于a[j]，则插入到数列中，所有数据往后移动
                    int temp = a[i];
                    for (int k = i; k > j; k--) {
                        a[k] = a[k - 1];
                    }
                    a[j] = temp;
                }
            }
            System.out.println("第 " + (++num) + " 趟排序： " + Arrays.toString(a));
        }
        return a;
    }
    // 冒泡排序算法
    public static int[] BubbleSort(int[] a) {
        int n = a.length;
        boolean swapped;
        int passNumber = 0;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    // 交换 arr[j] 和 arr[j+1]
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果没有发生交换，说明数组已经有序
            if (!swapped) break;
            System.out.println("第 " + (++passNumber) + " 趟排序： " + Arrays.toString(a));
        }
        return a;
    }
    // 希尔排序算法
    public static int[] ShellSort(int[] a) {
        int n = a.length;
        int passNumber = 0;
        // 选择一个间隔序列，这里使用的是Hibbard增量序列
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个间隔序列进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = a[i];
                int j;
                for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
                    a[j] = a[j - gap];
                }
                a[j] = temp;
            }
            System.out.println("第 " + (++passNumber) + " 趟排序（间隔为" + gap + "）： " + Arrays.toString(a));
        }
        return a;
    }
    // 快速排序算法
    public static void QuickSort(int[] array, int low, int high) {
        if (array == null || array.length == 0)
            return;
        if (low >= high)
            return;
        // 选择中间的元素作为基准数
        int middle = low + (high - low) / 2;
        int pivot = array[middle];
        // 分区过程
        int i = low, j = high;
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        // 递归排序基准数左右两部分
        System.out.println("分区后数组状态: " + Arrays.toString(array));
        if (low < j)
            QuickSort(array, low, j);
        if (high > i)
            QuickSort(array, i, high);
    }
    // 基数排序
    public static void radixSort(int[] array) {
        int[][] bucket = new int[10][array.length]; // 创建桶数组，用于存储数字
        int[] bucketIndex = new int[10]; // 创建桶索引数组，用于记录每个桶中数字的数量
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int maxLength = (max + "").length(); // 计算最大数字的位数
        for (int i = 0; i < maxLength; i++) {
            int div = (int) Math.pow(10, i); // 计算当前位数的除数
            for (int j = 0; j < array.length; j++) {
                int element = (array[j] / div) % 10; // 计算当前位数的数字
                bucket[element][bucketIndex[element]] = array[j]; // 将数字放入对应的桶中
                bucketIndex[element]++;
            }
            int index = 0;
            for (int k = 0; k < bucketIndex.length; k++) {
                if (bucketIndex[k] != 0) { // 如果当前桶中有数字
                    for (int j = 0; j < bucketIndex[k]; j++) {
                        array[index++] = bucket[k][j]; // 将桶中的数字取出放入原数组
                    }
                    bucketIndex[k] = 0; // 重置桶索引
                }
            }
            System.out.println("第" + (i + 1) + "次排序的结果为" + Arrays.toString(array)); // 输出当前趟排序的结果
        }
    }
    // 归并排序算法
    public static int[] mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int[] temp = new int[a.length]; // 创建一个临时数组用于归并过程
            int mid = (left + right) / 2;
            mergeSort(a, left, mid, temp); // 递归排序左半部分
            mergeSort(a, mid + 1, right, temp); // 递归排序右半部分
            merge(a, left, mid, right, temp); // 合并两个有序的子数组
        }
        return a;
    }
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp); // 递归排序左半部分
            mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分
            merge(arr, left, mid, right, temp); // 合并两个有序的子数组
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, t = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }
        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }

    // 选择排序算法
    public static int[] selectionSort(int[] a) {
        int n = a.length;
        int passNumber = 0;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换找到的最小元素和当前位置的元素
            if (minIndex != i) {
                int temp = a[minIndex];
                a[minIndex] = a[i];
                a[i] = temp;
            }
            System.out.println("第 " + (++passNumber) + " 趟排序: " + Arrays.toString(a));
        }
        return a;
    }
    // TimSort排序算法
    public static void timSort(int[] array) {
        // Java 8 中的 Arrays.sort() 使用的就是 TimSort
        // 记录排序的趟数
        int passNumber = 1;  // 从1开始计数
        Arrays.sort(array);
        System.out.println("第 " + passNumber + " 趟排序结果：" + Arrays.toString(array));
        System.out.println("TimSort 结束");
    }
}
